package com.yanceysong.codetop.s81_s90;

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Comparator;

/**
 * .@ClassName S85_Mid_179_最大数
 * .@Description
 * .@date 2024/6/5 下午3:36
 * .@Author yanceysong
 * .@Version 1.0
 */
public class S85_Mid_179_最大数 {

    /**
     * .S85_Mid_179_最大数
     * .<p>
     * .<a href="https://leetcode.cn/problems/largest-number/">...</a>
     * .<p>
     * .给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
     * .<p>
     * .注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
     * .<p>
     * .示例 1：
     * .<p>
     * .输入：nums = [10,2]
     * .输出："210"
     * .<p>
     * .示例 2：
     * .<p>
     * .输入：nums = [3,30,34,5,9]
     * .输出："9534330"
     * .<p>
     * .提示：
     * .<p>
     * .1 <= nums.length <= 100
     * .0 <= nums[i] <= 10^9
     * .<p>
     * .核心标签：贪心算法、排序、自定义比较器
     * .<p>
     * .解题思路：
     * .这是一个贪心算法问题，关键在于定义正确的排序规则。
     * .<p>
     * .核心思想：
     * .对于两个数字 a 和 b，如果拼接后 "ab" > "ba"，则 a 应该排在 b 前面。
     * .例如：a=3, b=30
     * .- "3" + "30" = "330"
     * .- "30" + "3" = "303"
     * .- 因为 "330" > "303"，所以 3 应该排在 30 前面
     * .<p>
     * .算法步骤：
     * .1. 将所有整数转换为字符串
     * .2. 使用自定义比较器排序：比较 (b+a) 和 (a+b) 的字典序
     * .3. 将排序后的字符串拼接起来
     * .4. 特殊处理：如果结果以 '0' 开头，说明所有数字都是 0，返回 "0"
     * .<p>
     * .关键洞察：
     * .1. 为什么这个贪心策略是正确的？
     * .   - 假设最优解中 a 在 b 前面，但 "ba" > "ab"
     * .   - 那么交换 a 和 b 的位置会得到更大的数，与假设矛盾
     * .   - 因此这个比较规则能保证得到最大数
     * .<p>
     * .2. 为什么要比较 "ab" 和 "ba" 而不是直接比较 a 和 b？
     * .   - 直接比较数值大小无法处理 [3, 30] 这种情况
     * .   - 3 < 30，但最优排列是 "330" 而不是 "303"
     * .<p>
     * .3. 特殊情况处理：
     * .   - 输入 [0, 0, 0] 应该返回 "0" 而不是 "000"
     * .<p>
     * .ASCII 图解示例：
     * .<p>
     * .示例 1：nums = [10, 2]
     * .<p>
     * .步骤1：转换为字符串数组
     * .["10", "2"]
     * .<p>
     * .步骤2：自定义排序
     * .比较 "10" 和 "2"：
     * .- "2" + "10" = "210"
     * .- "10" + "2" = "102"
     * .- "210" > "102"，所以 "2" 排在 "10" 前面
     * .<p>
     * .排序后：["2", "10"]
     * .<p>
     * .步骤3：拼接
     * ."2" + "10" = "210"
     * .<p>
     * .最终结果："210"
     * .<p>
     * .═══════════════════════════════════════════════════════════════
     * .<p>
     * .示例 2：nums = [3, 30, 34, 5, 9]
     * .<p>
     * .步骤1：转换为字符串数组
     * .["3", "30", "34", "5", "9"]
     * .<p>
     * .步骤2：自定义排序（比较过程）
     * .<p>
     * .比较 "9" vs "5"：  "95" vs "59"  → "95" > "59"  → 9 在前
     * .比较 "9" vs "34"： "934" vs "349" → "934" > "349" → 9 在前
     * .比较 "9" vs "3"：  "93" vs "39"  → "93" > "39"  → 9 在前
     * .比较 "9" vs "30"： "930" vs "309" → "930" > "309" → 9 在前
     * .<p>
     * .比较 "5" vs "34"： "534" vs "345" → "534" > "345" → 5 在前
     * .比较 "5" vs "3"：  "53" vs "35"  → "53" > "35"  → 5 在前
     * .比较 "5" vs "30"： "530" vs "305" → "530" > "305" → 5 在前
     * .<p>
     * .比较 "34" vs "3"： "343" vs "334" → "343" > "334" → 34 在前
     * .比较 "34" vs "30"："3430" vs "3034" → "3430" > "3034" → 34 在前
     * .<p>
     * .比较 "3" vs "30"： "330" vs "303" → "330" > "303" → 3 在前
     * .<p>
     * .排序后：["9", "5", "34", "3", "30"]
     * .<p>
     * .步骤3：拼接
     * ."9" + "5" + "34" + "3" + "30" = "9534330"
     * .<p>
     * .最终结果："9534330"
     * .<p>
     * .═══════════════════════════════════════════════════════════════
     * .<p>
     * .特殊情况：nums = [0, 0, 0]
     * .<p>
     * .步骤1：转换为字符串数组
     * .["0", "0", "0"]
     * .<p>
     * .步骤2：排序（所有元素相同，顺序不变）
     * .["0", "0", "0"]
     * .<p>
     * .步骤3：拼接
     * ."0" + "0" + "0" = "000"
     * .<p>
     * .步骤4：特殊处理
     * .首字符是 '0' → 返回 "0"
     * .<p>
     * .最终结果："0"
     * .<p>
     * .时间复杂度：O(n·log(n)·k)
     * .- n 是数组长度
     * .- 排序的时间复杂度是 O(n·log(n))
     * .- 每次比较两个字符串的时间复杂度是 O(k)，k 是字符串的平均长度
     * .- 总体：O(n·log(n)·k)
     * .<p>
     * .空间复杂度：O(n·k)
     * .- 需要创建字符串数组：O(n·k)
     * .- StringBuilder 拼接：O(n·k)
     * .- 排序的额外空间：O(log(n))
     * .- 总体：O(n·k)
     */
    public String largestNumber(int[] nums) {
        // 步骤1：将所有整数转换为字符串
        String[] numStrings = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            numStrings[i] = String.valueOf(nums[i]);
        }

        // 步骤2：使用自定义比较器排序
        // 比较规则：如果 (b+a) > (a+b)，则 b 应该排在 a 前面
        // 这样可以保证拼接后的数字最大

        // 可以用字符串自带的比较器，但是我觉得这是取巧的。不方便理解这个算法的思路
        // Arrays.sort(numStrings, (a, b) -> (b + a).compareTo(a + b));

        Arrays.sort(numStrings, new Comparator<String>() {
            /**
             * .自定义比较器：比较两个数字字符串拼接后的大小
             * .<p>
             * .核心思想：
             * .- 对于两个数字字符串 a 和 b
             * .- 比较 "a+b" 和 "b+a" 的字典序
             * .- 如果 "b+a" > "a+b"，则 b 应该排在 a 前面
             * .<p>
             * .为什么这样比较是正确的？
             * .- 例如：a="3", b="30"
             * .- "a+b" = "330"
             * .- "b+a" = "303"
             * .- 因为 "330" > "303"，所以 a 应该排在 b 前面
             * <p>
             * .字符串比较的原理：
             * .- Java 的 compareTo 方法按字典序比较
             * .- 从左到右逐个字符比较 ASCII 值
             * .- 例如："330" vs "303"
             * .  - 第1位：'3' == '3'，继续
             * .  - 第2位：'3' > '0'，返回正数
             * .  - 结论："330" > "303"
             * <p>
             * .为什么不能直接比较数字大小？
             * .- 如果直接比较 3 和 30，会得到 3 < 30
             * .- 但实际上 "330" > "303"，所以 3 应该排在 30 前面
             * .- 这就是为什么需要比较拼接后的字符串
             * <p>
             * .图解示例：
             * <p>
             * .比较 "3" 和 "30"：
             * .┌─────────────────────────────────┐
             * .│ a = "3", b = "30"               │
             * .│                                 │
             * .│ a + b = "3" + "30" = "330"      │
             * .│ b + a = "30" + "3" = "303"      │
             * .│                                 │
             * .│ 比较 "330" vs "303"：           │
             * .│   '3' == '3' ✓                  │
             * .│   '3' > '0' ✓                   │
             * .│ 结论："330" > "303"             │
             * .│                                 │
             * .│ 因此 a 应该排在 b 前面          │
             * .└─────────────────────────────────┘
             * <p>
             * .比较 "9" 和 "34"：
             * .┌─────────────────────────────────┐
             * .│ a = "9", b = "34"               │
             * .│                                 │
             * .│ a + b = "9" + "34" = "934"      │
             * .│ b + a = "34" + "9" = "349"      │
             * .│                                 │
             * .│ 比较 "934" vs "349"：           │
             * .│   '9' > '3' ✓                   │
             * .│ 结论："934" > "349"             │
             * .│                                 │
             * .│ 因此 a 应该排在 b 前面          │
             * .└─────────────────────────────────┘
             * <p>
             * 返回值说明：
             * - 返回负数：a 排在 b 前面（升序）
             * - 返回 0：a 和 b 相等
             * - 返回正数：b 排在 a 前面（降序）
             * <p>
             * 我们的目标是降序排列（大的在前），所以：
             * - 如果 "b+a" > "a+b"，返回正数，让 b 排在 a 前面
             * - 如果 "b+a" < "a+b"，返回负数，让 a 排在 b 前面
             * - 如果 "b+a" == "a+b"，返回 0，顺序无所谓
             */
            @Override
            public int compare(String a, String b) {
                // 步骤1：拼接两个字符串，得到两种不同的组合
                String ab = a + b;  // a 拼接 b，例如："3" + "30" = "330"
                String ba = b + a;  // b 拼接 a，例如："30" + "3" = "303"

                // 步骤2：将拼接后的字符串转换为 BigInteger
                // 为什么使用 BigInteger？
                // - 拼接后的数字可能非常大，超过 long 的范围
                // - 例如：两个 10^9 的数字拼接后是 10^18 级别，接近 long 的上限
                // - BigInteger 可以处理任意大小的整数
                BigInteger numAB = new BigInteger(ab);  // "330" → 330
                BigInteger numBA = new BigInteger(ba);  // "303" → 303

                // 步骤3：比较两个数字的大小
                // compareTo 方法返回值：
                // - 返回负数：numBA < numAB，即 ba < ab，a 应该排在 b 前面
                // - 返回 0：numBA == numAB，即 ba == ab，顺序无所谓
                // - 返回正数：numBA > numAB，即 ba > ab，b 应该排在 a 前面
                //
                // 我们的目标是降序排列（大的数字在前），所以：
                // - 如果 ba > ab（例如 303 < 330），返回负数，让 a 排在 b 前面
                // - 如果 ba < ab（例如 934 > 349），返回正数，让 b 排在 a 前面

                // 步骤4：返回比较结果
                return numBA.compareTo(numAB);

                // 完整示例：
                // 比较 "3" 和 "30"：
                // - ab = "330", ba = "303"
                // - numAB = 330, numBA = 303
                // - 303 < 330，返回负数
                // - 结果：a("3") 排在 b("30") 前面
                // - 最终拼接："3" + "30" = "330" ✓
                //
                // 比较 "9" 和 "34"：
                // - ab = "934", ba = "349"
                // - numAB = 934, numBA = 349
                // - 349 < 934，返回负数
                // - 结果：a("9") 排在 b("34") 前面
                // - 最终拼接："9" + "34" = "934" ✓
            }
        });

        // 步骤3：将排序后的字符串拼接起来
        StringBuilder result = new StringBuilder();
        for (String numStr : numStrings) {
            result.append(numStr);
        }

        // 步骤4：特殊处理：如果结果以 '0' 开头，说明所有数字都是 0
        // 例如 [0, 0, 0] 应该返回 "0" 而不是 "000"
        return result.charAt(0) == '0' ? "0" : result.toString();
    }

    public static void main(String[] args) {
        S85_Mid_179_最大数 solution = new S85_Mid_179_最大数();

        System.out.println("=== 最大数测试开始 ===");

        // 测试1: 示例1 - 简单情况
        System.out.println("\n--- 测试1: 示例1 [10,2] ---");
        testCase1(solution);

        // 测试2: 示例2 - 多个数字
        System.out.println("\n--- 测试2: 示例2 [3,30,34,5,9] ---");
        testCase2(solution);

        // 测试3: 全是0
        System.out.println("\n--- 测试3: 全是0 [0,0,0] ---");
        testAllZeros(solution);

        // 测试4: 单个数字
        System.out.println("\n--- 测试4: 单个数字 [1] ---");
        testSingleNumber(solution);

        // 测试5: 包含0的混合数组
        System.out.println("\n--- 测试5: 包含0 [0,5,10] ---");
        testWithZero(solution);

        // 测试6: 相同前缀的数字
        System.out.println("\n--- 测试6: 相同前缀 [12,121] ---");
        testSamePrefix(solution);

        // 测试7: 大数字
        System.out.println("\n--- 测试7: 大数字 [999999998,999999997,999999999] ---");
        testLargeNumbers(solution);

        // 测试8: 递增序列
        System.out.println("\n--- 测试8: 递增序列 [1,2,3,4,5] ---");
        testIncreasingSequence(solution);

        // 测试9: 递减序列
        System.out.println("\n--- 测试9: 递减序列 [5,4,3,2,1] ---");
        testDecreasingSequence(solution);

        // 测试10: 复杂情况
        System.out.println("\n--- 测试10: 复杂情况 [8,80,89,808,8089] ---");
        testComplexCase(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试1: 示例1
     * .输入：[10,2]
     * .期望输出："210"
     */
    private static void testCase1(S85_Mid_179_最大数 solution) {
        int[] nums = {10, 2};
        System.out.println("输入: " + Arrays.toString(nums));

        String result = solution.largestNumber(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 210");
        assert result.equals("210") : "结果应为 210";
        System.out.println("✓ 测试1通过");
    }

    /**
     * .测试2: 示例2
     * .输入：[3,30,34,5,9]
     * .期望输出："9534330"
     */
    private static void testCase2(S85_Mid_179_最大数 solution) {
        int[] nums = {3, 30, 34, 5, 9};
        System.out.println("输入: " + Arrays.toString(nums));

        String result = solution.largestNumber(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 9534330");
        assert result.equals("9534330") : "结果应为 9534330";
        System.out.println("✓ 测试2通过");
    }

    /**
     * .测试3: 全是0
     * .输入：[0,0,0]
     * .期望输出："0"
     */
    private static void testAllZeros(S85_Mid_179_最大数 solution) {
        int[] nums = {0, 0, 0};
        System.out.println("输入: " + Arrays.toString(nums));

        String result = solution.largestNumber(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 0");
        assert result.equals("0") : "全是0应该返回 0 而不是 000";
        System.out.println("✓ 测试3通过");
    }

    /**
     * .测试4: 单个数字
     * .输入：[1]
     * .期望输出："1"
     */
    private static void testSingleNumber(S85_Mid_179_最大数 solution) {
        int[] nums = {1};
        System.out.println("输入: " + Arrays.toString(nums));

        String result = solution.largestNumber(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 1");
        assert result.equals("1") : "结果应为 1";
        System.out.println("✓ 测试4通过");
    }

    /**
     * .测试5: 包含0的混合数组
     * .输入：[0,5,10]
     * .期望输出："5100"
     */
    private static void testWithZero(S85_Mid_179_最大数 solution) {
        int[] nums = {0, 5, 10};
        System.out.println("输入: " + Arrays.toString(nums));

        String result = solution.largestNumber(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 5100");
        assert result.equals("5100") : "结果应为 5100";
        System.out.println("✓ 测试5通过");
    }

    /**
     * .测试6: 相同前缀的数字
     * .输入：[12,121]
     * .期望输出："12121"
     * .解释：比较 "12121" vs "12112"，前者更大
     */
    private static void testSamePrefix(S85_Mid_179_最大数 solution) {
        int[] nums = {12, 121};
        System.out.println("输入: " + Arrays.toString(nums));

        String result = solution.largestNumber(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 12121");
        assert result.equals("12121") : "结果应为 12121";
        System.out.println("✓ 测试6通过");
    }

    /**
     * .测试7: 大数字
     * .输入：[999999998,999999997,999999999]
     * .期望输出："999999999999999998999999997"
     */
    private static void testLargeNumbers(S85_Mid_179_最大数 solution) {
        int[] nums = {999999998, 999999997, 999999999};
        System.out.println("输入: " + Arrays.toString(nums));

        String result = solution.largestNumber(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 999999999999999998999999997");
        assert result.equals("999999999999999998999999997") : "结果应为 999999999999999998999999997";
        System.out.println("✓ 测试7通过");
    }

    /**
     * .测试8: 递增序列
     * .输入：[1,2,3,4,5]
     * .期望输出："54321"
     */
    private static void testIncreasingSequence(S85_Mid_179_最大数 solution) {
        int[] nums = {1, 2, 3, 4, 5};
        System.out.println("输入: " + Arrays.toString(nums));

        String result = solution.largestNumber(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 54321");
        assert result.equals("54321") : "结果应为 54321";
        System.out.println("✓ 测试8通过");
    }

    /**
     * .测试9: 递减序列
     * .输入：[5,4,3,2,1]
     * .期望输出："54321"
     */
    private static void testDecreasingSequence(S85_Mid_179_最大数 solution) {
        int[] nums = {5, 4, 3, 2, 1};
        System.out.println("输入: " + Arrays.toString(nums));

        String result = solution.largestNumber(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 54321");
        assert result.equals("54321") : "结果应为 54321";
        System.out.println("✓ 测试9通过");
    }

    /**
     * .测试10: 复杂情况 - 数字之间有包含关系
     * .输入：[8,80,89,808,8089]
     * .期望输出："8908808880"
     * .解释：
     * .- "89" vs "8": "898" > "889" → 89 在前
     * .- "89" vs "80": "8980" > "8089" → 89 在前
     * .- "89" vs "808": "89808" > "80889" → 89 在前
     * .- "89" vs "8089": "898089" > "808989" → 89 在前
     * .- "808" vs "80": "80880" > "80808" → 808 在前
     * .- "808" vs "8": "8088" > "8808" → 808 在前
     * .- "8089" vs "80": "808980" > "808089" → 8089 在前
     * .- "80" vs "8": "808" > "880" → 80 在前
     */
    private static void testComplexCase(S85_Mid_179_最大数 solution) {
        int[] nums = {8, 80, 89, 808, 8089};
        System.out.println("输入: " + Arrays.toString(nums));

        String result = solution.largestNumber(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 8908808880");
        assert result.equals("8908808880") : "结果应为 8908808880";
        System.out.println("✓ 测试10通过");
    }
}

